package main

type Node struct {
	Val    int
	Next   *Node
	Random *Node
}

func copyRandomList(head *Node) *Node {
	if head == nil {
		return nil
	}
	oldNewMap := make(map[*Node]*Node)
	newHair := &Node{}
	n2 := newHair
	n := head
	for n != nil {
		tmp := &Node{
			Val: n.Val,
		}
		oldNewMap[n] = tmp
		n2.Next = tmp
		n2 = tmp
		n = n.Next
	}
	n = head
	n2 = newHair.Next
	for n != nil && n2 != nil {
		newRand := oldNewMap[n.Random]
		n2.Random = newRand
		n = n.Next
		n2 = n2.Next
	}
	return newHair.Next
}

func main() {

	n1 := &Node{Val: 1}
	n2 := &Node{Val: 2}
	n3 := &Node{Val: 3}
	
	n1.Next = n2
	n2.Next = n3

	n1.Random = n2
	n2.Random = n3

	head2 := copyRandomList(n1)
	println(head2)
}
